#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
//int main()
//{
//	int cnt = 0;
//	char str[1000] = { 0 };
//	gets(str);
//	char* ptrl = str;
//	char* ptrr = str;
//	while (*ptrl)
//	{
//		while (*(ptrl) == *(ptrr))
//		{
//			ptrr++;
//			cnt++;
//		}
//		printf("%d%c", cnt, *ptrl);
//		cnt = 0;
//		ptrl = ptrr;
//		
//	}
//	
//	return 0;
//}
////int main()
////{
////	int a, b, n,aim;
////	int flag = 1;
////	scanf("%d %d %d", &a, &b, &n);
////	for (int i = 1;i <= n;i++)
////	{
//		aim = a * 10 / b;
//		a = (a * 10) % b;
//		if (a == 0 &&i!=n)
//		{
//			flag = 0;
//			break;
//		}
//	}
//	if (flag)
//		printf("%d", aim);
//	else
//		printf("0");
//	return 0;
//}
//int main()
//{
//	char str[1000] = { 0 };
//	gets(str);
//	char arr[26] = { 0 };
//	for (int i = 0;i < strlen(str);i++)
//	{
//		arr[(str[i] - 'a')]++;
//	}
//	int Max = arr[25];
//	int k;
//	for (int j = 25;j >=0;j--)
//	{
//		if (Max <= arr[j])
//		{
//			Max = arr[j];
//			k = j;
//		}
//			
//	}
//	printf("%c %d", k + 'a', Max);
//	return 0;
//}
//int main()
//{
//	long long sum = 0;
//	int n = 0;
//	scanf("%d", &n);
//	long long  ret=1;
//	for (int i = 1;i <= n;i++)
//	{
//		ret *= i;
//		sum += ret;
//	}
////	printf("%lld", sum);
////	return 0;
////}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int sum[10000] = { 0 };
//	int arr[10000] = { 0 };
//	arr[0] = 1;
//	for (int i = 1;i <= n;i++)
//	{
//		int carry1 = 0;
//		for (int j = 0;j < 10000;j++)
//		{
//			int tmp=(arr[j] * i + carry1) / 10;
//			arr[j]=(arr[j] * i + carry1) % 10;
//			carry1 = tmp;
//		}
//		int carry2 = 0;
//		for (int k = 0;k < 10000;k++)
//		{
//			sum[k] = sum[k] + arr[k] + carry2;
//			int tmp = sum[k] / 10;
//			sum[k] %= 10;
//			carry2 = tmp;
//		}
//	}
//	int p = 9999;
//	while (!sum[p])
//	{
//		p--;
//	}
//	for (int q = p;q >= 0;q--)
//	{
//		printf("%d", sum[q]);
//	}
//
//
//	return 0;
//}
//int main()
//{
//	int sum, h, time;
//	scanf("%d %d %d", &sum, &h, &time);
//	if (sum * h <= time)
//		printf("0");
//	else
//	{
//		if ((time / h) == 0)
//		{
//			printf("%d", sum - (time / h));
//		}
//		else
//			printf("%d", sum - (time / h) - 1);
//	}
//	return 0;
//}
//#include<stdio.h>
//int main()
//{
//	int sum, h, time;
//	scanf("%d %d %d", &sum, &h, &time);
//	if (sum * h <= time)
//	{
//		printf("0");
//	}
//	else
//	{
//		if ((time % h) == 0)
//		{
//			printf("%d", sum - (time / h));
//		}
//		else
//		{
//			printf("%d", sum - (time / h) - 1);
//		}
//	}
//	return 0;
//}
//int main()
//{
//	int arr[4][5]={0};
//	for (int i = 0;i < 4;i++)
//	{
//		for (int j = 0;j < 5;j++)
//		{
//			scanf("%d", &arr[i][j]);
//		}
//	}
//	for (int i = 1;i < 3;i++)
//	{
//		for (int j = 1;j < 4;j++)
//		{
//			int sum = 0;
//			sum = arr[i][j] + arr[i-1][j] + arr[i+1][j] + arr[i][j-1] + arr[i][j+1];
//			double tmp=arr[i][j] / 5;
//			if (tmp > 2.5)
//			{
//				tmp + 1;
//			}
//			arr[i][j] = tmp;
//		}
//	}
//	for (int i = 0;i < 4;i++)
//	{
//		for (int j = 0;j < 5;j++)
//		{
//			printf("%d ", arr[i][j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}
//int main()
//{
//	int arr[4][5] = { 0 };
//	int str[4][5] = { 0 };
//	for (int i = 0;i < 4;i++)
//	{
//		for (int j = 0;j < 5;j++)
//		{
//			scanf("%d", &arr[i][j]);
//
//		}
//	}
//	for (int i=0;i<4;i++)
//	{
//		for (int j = 0;j < 5;j++)
//		{
//			if (i == 0 || j == 0 || i == 3 || j == 4)
//			{
//				str[i][j] = arr[i][j];
//			}
//			else {
//				int sum = 0;
//				sum = arr[i][j] + arr[i - 1][j] + arr[i + 1][j] + arr[i][j - 1] + arr[i][j + 1];
//				double tmp = sum % 5;
//				str[i][j] = sum / 5;
//				if (tmp > 2.5)
//				{
//					str[i][j]++;
//				}
//				
//			}
//		}
//	}for (int i = 0;i < 4;i++)
//	{
//		for (int j = 0;j < 5;j++)
//		{
//			printf("%d ", str[i][j]);
//		}
//		printf("\n");
//	}
//	return 0;
//}